home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / man / lib / c / List.man < prev    next >
Encoding:
Text File  |  1989-12-14  |  9.8 KB  |  387 lines
  1. ' $Header: /sprite/src/lib/c/list/RCS/List.man,v 1.2 89/12/14 12:27:51 shirriff Exp $ SPRITE (Berkeley)
  2. .so \*(]ltmac.sprite
  3. .HS List lib
  4. .BS
  5. .SH NAME
  6. List \- overview of circular linked list routines.
  7. .SH SYNOPSIS
  8. .nf
  9. \fB#include <list.h>\fR
  10. .sp
  11. \fBList_Init\fR(\fIheaderPtr\fP)
  12. \fBList_InitElement\fR(\fIitemPtr\fP)
  13. \fBList_Insert\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  14. \fBList_ListInsert\fR(\fIheaderPtr\fP, \fIdestPtr\fP)
  15. \fBList_Remove\fR(\fIitemPtr\fP)
  16. \fBList_Move\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  17. .sp
  18. \fBLIST_AFTER\fR(\fIitemPtr\fP)
  19. \fBLIST_BEFORE\fR(\fIitemPtr\fP)
  20. \fBLIST_ATFRONT\fR(\fIheaderPtr\fP)
  21. \fBLIST_ATREAR\fR(\fIheaderPtr\fP)
  22. .sp
  23. \fBLIST_FORALL\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  24. .sp
  25. \fBList_IsEmpty\fR\fR\fB(\fIheaderPtr\fP)
  26. \fBList_IsAtEnd\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  27. \fBList_First\fR\fR\fB(\fIheaderPtr\fP)
  28. \fBList_Last\fR\fR\fB(\fIheaderPtr\fP)
  29. \fBList_Prev\fR\fR\fB(\fIitemPtr\fP)
  30. \fBList_Next\fR\fR\fB(\fIitemPtr\fP)
  31. .SH ARGUMENTS
  32. .AS List_Links *headerPtr in
  33. .AP List_Links *headerPtr in
  34. Pointer to the header of a list.
  35. .AP List_Links *itemPtr in 
  36. Pointer to a member of a list (possibly the header).
  37. .AP List_Links *destPtr in 
  38. Pointer to the member after which to insert or move another member.
  39. .BE
  40.  
  41. .SH INTRODUCTION
  42. .PP
  43. The \fBList_\fR\ routines define the ``list'' abstraction, 
  44. which enables one to link
  45. together arbitrary data structures.  Lists are doubly-linked and
  46. circular.  A list contains a header followed by its real members, if
  47. any.  (An empty list therefore consists of a single element, the
  48. header,  whose \fInextPtr\fR and \fIprevPtr\fR fields point to itself).
  49. To refer
  50. to a list as a whole, the user keeps a pointer to the header; that
  51. header is initialized by a call to \fBList_Init()\fR, which
  52. creates an empty
  53. list given a pointer to a List_Links structure (described below).
  54. .PP
  55. The links are contained in a two-element structure called List_Links.
  56. A list joins List_Links records (that is, each List_Links structure
  57. points to other List_Links structures), but if the List_Links is the
  58. first field within a larger structure, then the larger structures are
  59. effectively linked together as shown in Figure 1.
  60. .if t \{
  61. .bp
  62. .sp 2
  63. .br
  64. .nr g1 999u
  65. .nr g2 499u
  66. .GS C
  67. .nr g3 \n(.f
  68. .nr g4 \n(.s
  69. \0
  70. .sp -1
  71. \D's -1u'\D't 5u'
  72. .sp -1
  73. \D'l 0u 499u'\D'l 999u 0u'\D'l 0u -499u'\D'l -999u 0u'
  74. .sp -1
  75. .ft R
  76. .ps 16
  77. .nr g8 \n(.d
  78. .ds g9 "Figure 1: Structure of a list.
  79. .sp 443u
  80. \h'110u'\&\*(g9
  81. .sp |\n(g8u
  82. \D's 4u'\D't 1u'
  83. .sp -1
  84. .sp 165u
  85. \h'825u'\D'l -166u 0u'
  86. .sp -1
  87. .ft R
  88. .ps 36
  89. .nr g8 \n(.d
  90. .ds g9 "...
  91. .sp 146u
  92. \h'756u'\h-\w\*(g9u/2u\&\*(g9
  93. .sp |\n(g8u
  94. .ft R
  95. .ps 16
  96. .nr g8 \n(.d
  97. .ds g9 "struct
  98. .sp 112u
  99. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  100. .sp |\n(g8u
  101. .ft R
  102. .ps 16
  103. .nr g8 \n(.d
  104. .ds g9 "rest of
  105. .sp 49u
  106. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  107. .sp |\n(g8u
  108. \D's -1u'\D't 3u'
  109. .sp -1
  110. .sp -97u
  111. \h'659u'\D'l 0u 264u'\D'l 166u 0u'\D'l 0u -264u'\D'l -166u 0u'
  112. .sp -1
  113. \D't 1u'
  114. .sp -1
  115. .sp 77u
  116. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  117. .sp -1
  118. .ft R
  119. .ps 10
  120. .nr g8 \n(.d
  121. .ds g9 "List_Links
  122. .sp -21u
  123. \h'742u'\h-\w\*(g9u/2u\&\*(g9
  124. .sp |\n(g8u
  125. .ft R
  126. .ps 16
  127. .nr g8 \n(.d
  128. .ds g9 "first elt.
  129. .sp -91u
  130. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  131. .sp |\n(g8u
  132. \D's 4u'
  133. .sp -1
  134. .sp 20u
  135. \h'339u'\D'l -166u 0u'
  136. .sp -1
  137. .ft R
  138. .ps 36
  139. .nr g8 \n(.d
  140. .ds g9 "...
  141. .sp 146u
  142. \h'256u'\h-\w\*(g9u/2u\&\*(g9
  143. .sp |\n(g8u
  144. .ft R
  145. .ps 16
  146. .nr g8 \n(.d
  147. .ds g9 "struct
  148. .sp 112u
  149. \h'249u'\h-\w\*(g9u/2u\&\*(g9
  150. .sp |\n(g8u
  151. .ft R
  152. .ps 16
  153. .nr g8 \n(.d
  154. .ds g9 "rest of
  155. .sp 49u
  156. \h'249u'\h-\w\*(g9u/2u\&\*(g9
  157. .sp |\n(g8u
  158. \D's -1u'\D't 3u'
  159. .sp -1
  160. .sp -97u
  161. \h'173u'\D'l 0u 264u'\D'l 166u 0u'\D'l 0u -264u'\D'l -166u 0u'
  162. .sp -1
  163. .ft R
  164. .ps 36
  165. .nr g8 \n(.d
  166. .ds g9 "...
  167. .sp 28u
  168. \h'61u'\h-\w\*(g9u/2u\&\*(g9
  169. .sp |\n(g8u
  170. .ft R
  171. .ps 36
  172. .nr g8 \n(.d
  173. .ds g9 "...
  174. .sp 77u
  175. \h'61u'\h-\w\*(g9u/2u\&\*(g9
  176. .sp |\n(g8u
  177. .ft R
  178. .ps 36
  179. .nr g8 \n(.d
  180. .ds g9 "...
  181. .sp 77u
  182. \h'950u'\h-\w\*(g9u/2u\&\*(g9
  183. .sp |\n(g8u
  184. .ft R
  185. .ps 36
  186. .nr g8 \n(.d
  187. .ds g9 "...
  188. .sp 35u
  189. \h'950u'\h-\w\*(g9u/2u\&\*(g9
  190. .sp |\n(g8u
  191. \D't 1u'
  192. .sp -1
  193. .sp 77u
  194. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  195. .sp -1
  196. \h'902u'\D'l -77u 0u'
  197. .sp -1
  198. \h'659u'\D'l -77u 0u'
  199. .sp -1
  200. \h'582u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  201. .sp -1
  202. \h'416u'\D'l -77u 0u'
  203. .sp -1
  204. \h'96u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  205. .sp -1
  206. \h'173u'\D'l -77u 0u'
  207. .sp -1
  208. .ft R
  209. .ps 10
  210. .nr g8 \n(.d
  211. .ds g9 "List_Links
  212. .sp -21u
  213. \h'256u'\h-\w\*(g9u/2u\&\*(g9
  214. .sp |\n(g8u
  215. .sp -49u
  216. \h'905u'\D'l -9u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 9u -6u'
  217. .sp -1
  218. \h'829u'\D'l 76u 0u'
  219. .sp -1
  220. \h'582u'\D'l 77u 0u'
  221. .sp -1
  222. \h'659u'\D'l -10u -6u'\D'l 4u 6u'\D'l -4u 6u'\D'l 10u -6u'
  223. .sp -1
  224. .ft R
  225. .ps 16
  226. .nr g8 \n(.d
  227. .ds g9 "last elt.
  228. .sp -42u
  229. \h'263u'\h-\w\*(g9u/2u\&\*(g9
  230. .sp |\n(g8u
  231. \h'416u'\D'l -10u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 10u -6u'
  232. .sp -1
  233. \h'339u'\D'l 77u 0u'
  234. .sp -1
  235. \h'173u'\D'l -10u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 10u -6u'
  236. .sp -1
  237. \h'96u'\D'l 77u 0u'
  238. .sp -1
  239. .ft R
  240. .ps 16
  241. .nr g8 \n(.d
  242. .ds g9 "header
  243. .sp -42u
  244. \h'499u'\h-\w\*(g9u/2u\&\*(g9
  245. .sp |\n(g8u
  246. \D't 3u'
  247. .sp -1
  248. .sp -28u
  249. \h'416u'\D'l 0u 97u'\D'l 166u 0u'\D'l 0u -97u'\D'l -166u 0u'
  250. .sp -1
  251. .ft R
  252. .ps 10
  253. .nr g8 \n(.d
  254. .ds g9 "List_Links
  255. .sp 56u
  256. \h'506u'\h-\w\*(g9u/2u\&\*(g9
  257. .sp |\n(g8u
  258. \D't 1u'
  259. .sp -1
  260. .sp 77u
  261. \h'339u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  262. .sp -1
  263. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  264. .sp -1
  265. .sp 354u
  266. \D't 3u'\D's -1u'
  267. .br
  268. .ft \n(g3
  269. .ps \n(g4
  270. .GE
  271. .\}
  272. .PP
  273. A typical structure might be something like:
  274.  
  275. .nf
  276.      typedef struct {
  277.                  List_Links links;
  278.                  char ch;
  279.                  int flags;
  280.      } EditChar;
  281. .fi
  282. .LP
  283. It is possible to link structures through List_Links fields that are
  284. not at the beginning of the larger structure, but it is then necessary
  285. to perform an additional pointer indirection to find the beginning of
  286. the larger 
  287. structure, given a pointer to some point within it.  The easiest way to do 
  288. this is to define a structure that contains a List_Links field and a pointer
  289. to the larger structure, such as:
  290. .nf
  291.      typedef struct {
  292.                  List_Links links;
  293.                  LargeStruct *structPtr;
  294.      } LargeStructLink;
  295. .fi
  296. .LP
  297. By including a ``LargeStructLink'' within a ``LargeStruct'' and setting the
  298. structPtr field of the LargeStructLink to point to the LargeStruct
  299. itself, LargeStruct structures may be linked together in a list
  300. that is contained in the middle of the structure rather than the beginning.
  301.  
  302. .SH USAGE
  303. .PP
  304. After a list has been initialized by calling \fBList_Init\fR, elements may
  305. be inserted, deleted, or moved within the list.  
  306. Before an element is inserted in a list for the first time it must
  307. be initialized by calling the routine \fBList_InitElement\fR.  To insert a
  308. List_Links element into a list, \fBList_Insert\fR is called with two
  309. arguments.  The first argument is a pointer to the structure to be
  310. inserted into a list, and the second argument is a pointer to the list
  311. member after which it is to be inserted.  Typically, the following
  312. macros are used to select the insertion point or the destination of a
  313. \fBList_Move\fR:
  314. .IP
  315. .RS
  316. .IP "\(bu \fBLIST_BEFORE\fR(\fIitemPtr\fR)" 30
  317. Insert the element before \fI*itemPtr\fR.
  318. .IP "\(bu \fBLIST_AFTER\fR(\fIitemPtr\fR)" 30
  319. Insert the element after \fI*itemPtr\fR.
  320. .IP "\(bu \fBLIST_ATFRONT\fR(\fIheaderPtr\fR)" 30
  321. Insert the element at the front of the list.
  322. .IP "\(bu \fBLIST_ATREAR\fR(\fIheaderPtr\fR)" 30
  323. Insert the element at the end of the list.
  324. .RE
  325. .VS
  326. .PP
  327. To insert a list into another list, call \fBList_ListInsert\fR with the
  328. header of the list to be inserted and a pointer to the member of the second
  329. list after which the first list is to be inserted.  After calling
  330. \fBList_ListInsert\fP, the header of the first list is no longer valid
  331. and may be destroyed.
  332. .VE
  333. .PP
  334. To remove a structure from a list, call \fBList_Remove\fR with a
  335. pointer to the structure to be removed.  
  336. To move a structure, call \fBList_Move\fR with two arguments: a pointer to
  337. the structure to be moved, and a pointer to the structure after which
  338. it is to be placed.  \fBList_Move\fR(\fIitemPtr\fR, \fIdestPtr\fR) is therefore
  339. equivalent to \fBList_Remove\fR(\fIitemPtr\fR) followed by \fBList_Insert\fR(\fIitemPtr\fR,
  340. \fIdestPtr\fR).
  341.  
  342. .SH ADDITIONAL UTILITIES
  343. .PP
  344. Several other macros are available for the manipulation of List_Links.
  345. \fBLIST_FORALL\fR(\fIheaderPtr\fR, \fIitemPtr\fR) is used to step through each element
  346. in the list pointed to by headerPtr, setting itemPtr to point to each
  347. element in turn.  \fBLIST_FORALL\fR is used typically by casting \fIitemPtr\fR as
  348. a pointer to the entire structure, as in:
  349. .nf
  350.     List_Links *headerPtr;    /* pointer to head of existing list */
  351.     List_Links *itemPtr;    /* place-holder during loop */
  352.     EditChar   *charPtr;    /* pointer to entire EditChar structure */
  353.  
  354.     LIST_FORALL(headerPtr, itemPtr) {
  355.         charPtr = (EditChar *) itemPtr;
  356.         /* operations using charPtr */
  357.     }
  358. .fi
  359. .PP
  360. The following macros may be useful to those who use List_Links at a
  361. ``lower'' level than looping through an entire list:
  362. .RS
  363. .IP "\(bu \fBList_IsEmpty\fR(\fIheaderPtr\fR) " 30
  364. returns TRUE if \fIheaderPtr\fR points to an empty
  365. list.
  366. .IP "\(bu \fBList_IsAtEnd\fR(\fIheaderPtr\fR, \fIitemPtr\fR)" 30
  367. returns TRUE if \fIitemPtr\fR is
  368. past the end of the list; i.e., it points to the header.
  369. .IP "\(bu \fBList_First\fR(\fIheaderPtr\fR) " 30
  370. .IP "\(bu \fBList_Last\fR(\fIheaderPtr\fR) " 30
  371. \fBList_First\fR returns the first member in a list, and
  372. \fBList_Last\fR returns the last member.  If the list is empty,
  373. the header is considered to be the first and last member.
  374. .IP "\(bu \fBList_Prev\fR(\fIitemPtr\fR) " 30
  375. returns a pointer to the member preceding the given
  376. member in its list.
  377. Note:  if the given member is the first element
  378. of the list, \fBList_Prev\fR will return the list header.
  379. .IP "\(bu \fBList_Next\fR(\fIitemPtr\fR)" 30
  380. returns the next
  381. member of the list.
  382. Note:  if the given member is the last element
  383. of the list, \fBList_Next\fR will return the list header.
  384. .RE
  385. .SH KEYWORDS
  386. list, linked, circular, List_Links, data structures
  387.